#include <iostream>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};
//判断是否为完全二叉树
bool IsCompleteBinaryTree(TreeNode* root)
{
    if(root == nullptr) return true;

    queue<TreeNode*> q;//定义一个队列，类型是TreeNode
    q.push(root);

    bool mustBeLeaf = false;//标记是否到了必须为叶子的阶段
    while(!q.empty())
    {
        TreeNode* node = q.front();
        q.pop();

        if(mustBeLeaf)
        {
            if(node != nullptr) return false;
        }
        else
        {
            if(node == nullptr)
            {
                mustBeLeaf = true;
            }
            else
            {
                q.push(node->left);
                q.push(node->right);
            }
        }
    }
    return true;
}

int main()
{
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    if(IsCompleteBinaryTree(root))
    {
        cout<< "该二叉树是完全二叉树"<<endl;
    }
    else
    {
        cout<<"该二叉树不是完全二叉树"<<endl;
    }

    return 0;
}